/**
 * @file perft.c
 *
 * @brief Move generator test.
 *
 * @date 1998 - 2011
 * @author Richard Delorme
 * @version 4.1
 */

#include "bit.h"
#include "board.h"
#include "move.h"
#include "options.h"
#include "settings.h"
#include "util.h"

#include <stdlib.h>

/** hashing global data */
extern unsigned long long hash_rank[16][256];

/**
 * Gathered statistiscs
 */
typedef struct {
	unsigned long long n_nodes;  /*< node number */
	unsigned long long n_draws;  /*< number of draws */
	unsigned long long n_losses; /*< number of losses */
	unsigned long long n_wins;   /*< number of wins */
	unsigned long long n_passes; /*< number of passes */
	unsigned int min_mobility;   /*< min mobility */
	unsigned int max_mobility;   /*< max mobility */
} GameStatistics;

/** initial statistics*/
const GameStatistics GAME_STATISTICS_INIT = {0ULL, 0ULL, 0ULL, 0ULL, 0ULL, 64, 0};

/** 
 * @brief Accumulate statistics: add local data to global ones.
 * @param global Global statistics.
 * @param local Local statistics.
 */
void game_statistics_cumulate(GameStatistics *global, const GameStatistics *local)
{
	global->n_nodes += local->n_nodes;
	global->n_draws += local->n_draws;
	global->n_losses += local->n_losses;
	global->n_wins += local->n_wins;
	global->n_passes += local->n_passes;
	if (global->min_mobility > local->min_mobility) global->min_mobility = local->min_mobility;
	if (global->max_mobility < local->max_mobility) global->max_mobility = local->max_mobility;
}


/**
 * @brief Move generator performance test function.
 *
 * @param board
 * @param depth
 * @param global_stats statistics
 */
static void count_game(const Board *board, const int depth, GameStatistics *global_stats)
{
	GameStatistics stats = GAME_STATISTICS_INIT;
	unsigned long long moves;
	int x;
	Board next[1];

	if (depth == 1) {
		moves = get_moves(board->player, board->opponent);
		stats.n_nodes = stats.max_mobility = stats.min_mobility = bit_count(moves);
		if (moves == 0) {
			if (can_move(board->opponent, board->player)) {
				stats.n_passes = 1;
			} else {
				const int n_player = bit_count(board->player);
				const int n_opponent = bit_count(board->opponent);
				if (n_player > n_opponent) stats.n_wins = 1;
				else if (n_player == n_opponent) stats.n_draws = 1;
				else stats.n_losses = 1;
			}
		}
	} else {
		moves = get_moves(board->player, board->opponent);
		if (moves) {
			foreach_bit (x, moves) {
				board_next(board, x, next);
				count_game(next, depth - 1, &stats);
			}
		} else {
			board_next(board, PASS, next);
			if (can_move(next->player, next->opponent)) {
				count_game(next, depth - 1, &stats);
			}
		}
	}
	game_statistics_cumulate(global_stats, &stats);
}

/**
 * @brief Move generator performance test
 *
 * @param board
 * @param depth
 */
void count_games(const Board *board, const int depth)
{
	int i;
	unsigned long long t, n;
	GameStatistics stats;

	board_print(board, BLACK, stdout);
	puts("\n  ply           nodes        passes          wins         draws        losses    mobility        time   speed");
	puts("------------------------------------------------------------------------------------------------------------------");
	n = 1;
	for (i = 1; i <= depth; ++i) {
		stats = GAME_STATISTICS_INIT;
		t = -cpu_clock();
		count_game(board, i, &stats);
		t += cpu_clock();
		printf("  %2d, %15llu, %12llu, %12llu, %12llu, %12llu, ", i, stats.n_nodes + stats.n_passes, stats.n_passes, stats.n_wins, stats.n_draws, stats.n_losses);
		printf("  %2d - %2d, ", stats.min_mobility, stats.max_mobility);
		n += stats.n_nodes + stats.n_passes;
		time_print(t, stdout);	printf(", ");
		print_scientific(n / (0.001 * t + 0.001), "N/s\n", stdout);
		if (stats.n_nodes + stats.n_passes == 0) break;
	}
	printf("Total %12llu\n", n);
	puts("------------------------------------------------------------------------------------------------------------------");
}

/**
 * Hash entry;
 */
typedef struct {
	Board board;             /**< board */
	GameStatistics stats;    /**< statistics */
	int depth;               /**< depth */
} GameHash;

/** Hash entry initial value */
const GameHash GAME_HASH_INIT = {{0ULL, 0ULL}, {0ULL, 0ULL, 0ULL, 0ULL, 0ULL, 64, 0}, 0};

/** HashTable */
typedef struct {
	GameHash *array; /**< array of hash entries */
	int size;          /**< size */
    int mask;          /**< mask */
	unsigned long long n_tries; /**< n_tries */
	unsigned long long n_hits;  /**< n_tries */
} GameHashTable;	

/**
 * @brief Hash table initialisation
 *
 * @param hash Hash table.
 * @param bitsize Hash table size (as log2(size)).
 */
static void gamehash_init(GameHashTable *hash, int bitsize)
{
	int i;

	hash->size = (1 << bitsize) + 3;
	hash->mask = (1 << bitsize) - 1;
	hash->array = malloc((hash->size) * sizeof(GameHash));
	if (hash->array == NULL) fatal_error("Cannot allocate qperft hashtable.\n");
	for (i = 0; i < hash->size; ++i) hash->array[i] = GAME_HASH_INIT;
	hash->n_tries = hash->n_hits = 0;
}

/**
 * @brief Hash table resource freeing.
 *
 * @param hash Hash table.
 */
static void gamehash_delete(GameHashTable *hash)
{
	free(hash->array);
}

/**
 * @brief Store a game position.
 *
 * @param  hash Hash table.
 * @param b position.
 * @param depth Depth.
 * @param stats position's statistics.
 */
static void gamehash_store(GameHashTable *hash, const Board *b, const int depth, const GameStatistics *stats)
{
	Board u;
	GameHash *i, *j;

	if (depth > 2) {
		board_unique(b, &u);
		i = j = hash->array + (board_get_hash_code(&u) & hash->mask);

		++j; if (i->stats.n_nodes > j->stats.n_nodes) i = j;
		++j; if (i->stats.n_nodes > j->stats.n_nodes) i = j;
		++j; if (i->stats.n_nodes > j->stats.n_nodes) i = j;
		i->board = u;
		i->stats = *stats;
		i->depth = depth;
	}
}

/**
 * @brief Seek for a position in the hash table.
 *
 * @param  hash Hash table.
 * @param b position.
 * @param depth Depth.
 * @param stats position's statistics.
 * @return true if no position is found, false otherwise.
 */
static bool gamehash_fail(GameHashTable *hash, const Board *b, const int depth, GameStatistics *stats)
{
	Board u;
	GameHash *i, *j;

	if (depth > 2) {

		board_unique(b, &u);
		j = hash->array + (board_get_hash_code(&u) & hash->mask);
		++hash->n_tries;

		for (i = j; i < j + 4; ++i) {
			if (depth == i->depth && i->board.player == u.player && i->board.opponent == u.opponent) {
				*stats = i->stats;
				++hash->n_hits;
				return false;
			}
		}

	}

	return true;
}


/**
 * @brief Count games recursively.
 *
 * @param  hash Hash table.
 * @param board position.
 * @param depth Depth.
 * @param global_stats Game's statistics.
 */
static void quick_count_game(GameHashTable *hash, const Board *board, const int depth, GameStatistics *global_stats)
{
	GameStatistics stats = GAME_STATISTICS_INIT;
	unsigned long long moves;
	int x;
	Board next[1];

	if (depth == 1) {
		moves = get_moves(board->player, board->opponent);
		stats.n_nodes = stats.max_mobility = stats.min_mobility = bit_count(moves);
		if (moves == 0) {
			if (can_move(board->opponent, board->player)) {
				stats.n_passes = 1;
			} else {
				const int n_player = bit_count(board->player);
				const int n_opponent = bit_count(board->opponent);
				if (n_player > n_opponent) stats.n_wins = 1;
				else if (n_player == n_opponent) stats.n_draws = 1;
				else stats.n_losses = 1;
			}
		}
	} else if (gamehash_fail(hash, board, depth, &stats)) {
		moves = get_moves(board->player, board->opponent);
		if (moves) {
			foreach_bit (x, moves) {
				board_next(board, x, next);
				quick_count_game(hash, next, depth - 1, &stats);
			}
		} else {
			board_next(board, PASS, next);
			if (can_move(next->player, next->opponent)) {
				quick_count_game(hash, next, depth - 1, &stats);
			}
		}
		gamehash_store(hash, board, depth, &stats);
	}
	game_statistics_cumulate(global_stats, &stats);
}

/**
 * @brief Count games.
 *
 * @param board position.
 * @param depth Depth.
 */
void quick_count_games(const Board *board, const int depth)
{
	int i;
	long long t;
	GameHashTable hash;
	GameStatistics stats;
	unsigned long long n;

	board_print(board, BLACK, stdout);
	puts("\n  ply           nodes        passes          wins         draws        losses    mobility        time   speed");
	puts("------------------------------------------------------------------------------------------------------------------");
	n = 1;
	for (i = 1; i <= depth; ++i) {
		t = -cpu_clock();
		gamehash_init(&hash, options.hash_table_size);
		stats = GAME_STATISTICS_INIT;
		quick_count_game(&hash, board, i, &stats);
		t += cpu_clock();
		printf("  %2d, %15llu, %12llu, %12llu, %12llu, %12llu, ", i, stats.n_nodes + stats.n_passes, stats.n_passes, stats.n_wins, stats.n_draws, stats.n_losses);
		printf("  %2d - %2d, ", stats.min_mobility, stats.max_mobility);
		time_print(t, stdout);	printf(", ");
		n += stats.n_nodes + stats.n_passes;
		print_scientific(n / (0.001 * t + 0.001), "N/s,", stdout);
		printf("  (h_tries = %lld, h_hits = %lld)\n", hash.n_tries, hash.n_hits);
		gamehash_delete(&hash);
		if (stats.n_nodes + stats.n_passes == 0) break;
	}
	printf("Total %12llu\n", n);
	puts("------------------------------------------------------------------------------------------------------------------");
}


/**
 * Array of position.
 */
typedef struct {
	Board *item; /**< dynamic array */
	int n;       /**< number of items in the array */
	int size;    /**< capacity of the array */
} PosArray;

/**
 * @brief array initialisation.
 * @param array Array of positions.
 */
static void positionarray_init(PosArray *array)
{
	array->item = NULL;
	array->n = array->size = 0;
}

/**
 * @brief array supression.
 * @param array Array of positions.
 */
static void positionarray_delete(PosArray *array)
{
	free(array->item);
}

/**
 * @brief Append a position into the array.
 * @param array Array of positions.
 * @param b Position.
 */
static bool positionarray_append(PosArray *array, const Board *b)
{
	int i;

	for (i = 0; i < array->n; ++i) {
		if (board_equal(array->item + i, b)) return false;
	}

	if (array->size < array->n + 1) {
		array->item = realloc(array->item, (array->size = (array->size + (array->size >> 1) + 1)) * sizeof (Board));
		if (array->item == NULL) fatal_error("Cannot re-allocate board array.\n");
	}
	array->item[array->n++] = *b;
	return true;
}


/**
 * HashTable of positions
 */
typedef struct {
	PosArray *array;
	int size;
	int mask;
} PositionHash;

/**
 * @brief Initialisation of the hash table.
 * @param hash Hash table.
 * @param bitsize Hash table size (as log2(size)).
 */
static void positionhash_init(PositionHash *hash, int bitsize)
{
	int i;

	hash->size = (1 << bitsize);
	hash->mask = hash->size - 1;
	hash->array = malloc(hash->size * sizeof(PosArray));
	if (hash->array == NULL) fatal_error("Cannot re-allocate board array.\n");
	for (i = 0; i < hash->size; ++i) positionarray_init(hash->array + i);
}

/**
 * @brief Free the hash table.
 * @param hash Hash table.
 */
static void positionhash_delete(PositionHash *hash)
{
	int i;

	for (i = 0; i < hash->size; ++i) positionarray_delete(hash->array + i);
	free(hash->array);
}

/**
 * @brief Append a position to the hash table.
 * @param hash Hash table.
 * @param b Position.
 */
static bool positionhash_append(PositionHash *hash, const Board *b)
{
	Board u;

	board_unique(b, &u);
	return positionarray_append(hash->array + (board_get_hash_code(&u) & hash->mask), &u);
}

/**
 * @brief Recursively count positions.
 * @param hash Hash table.
 * @param board position.
 * @param depth depth.
 */
static unsigned long long count_position(PositionHash *hash, const Board *board, const int depth)
{
	unsigned long long nodes = 0;
	unsigned long long moves;
	int x;
	Board next[1];

	if (positionhash_append(hash, board)) {
		if (depth == 0) return 1;
		moves = get_moves(board->player, board->opponent);

		if (moves) {
			foreach_bit (x, moves) {
				board_next(board, x, next);
				nodes += count_position(hash, next, depth - 1);
			}
		} else {
			board_next(board, PASS, next);
			nodes += count_position(hash, next, depth - 1);
		}
	}

	return nodes;
}

/**
 * @brief Count positions.
 * @param board position.
 * @param depth depth.
 */
void count_positions(const Board *board, const int depth)
{
	int i;
	unsigned long long n, c;
	long long t;
	PositionHash hash;


	board_print(board, BLACK, stdout);
	puts("\n depth       nodes        cumul.        time  speed");
	puts("-------------------------------------------------------");
	c = 1;
	for (i = 1; i <= depth; ++i) {
		positionhash_init(&hash, options.hash_table_size);
		t = -cpu_clock();
		c += (n = count_position(&hash, board, i));
		t += cpu_clock();
		printf("  %2d, %12llu, %12llu, ", i, n, c);
		time_print(t, stdout);	printf(", ");
		print_scientific(n / (0.001 * t + 0.001), "N/s\n", stdout);
		positionhash_delete(&hash);
	}
	puts("-------------------------------------------------------");
}

/**
 * @brief unique shape.
 *
 * @param shape input Shape.
 * @return 
 */
unsigned long long shape_unique(unsigned long long shape)
{
	unsigned long long sym, unique;
	int i;

	unique = shape;
	for (i = 1; i < 8; ++i) {
		sym = shape;
		if (i & 1) sym = horizontal_mirror(sym);
		if (i & 2) sym = vertical_mirror(sym);
		if (i & 4) sym = transpose(sym);
		if (unique > sym) unique = sym;
	}

	return unique;
}

/**
 * @brief Compute a hash code.
 *
 * @param shape Board shape.
 * @return The hash code of the bitboard.
 */
unsigned long long shape_get_hash_code(const unsigned long long shape)
{
	unsigned long long h;
	const unsigned char *p = (const unsigned char*)&shape;

	h  = hash_rank[0][p[0]];
	h ^= hash_rank[1][p[1]];
	h ^= hash_rank[2][p[2]];
	h ^= hash_rank[3][p[3]];
	h ^= hash_rank[4][p[4]];
	h ^= hash_rank[5][p[5]];
	h ^= hash_rank[6][p[6]];
	h ^= hash_rank[7][p[7]];
	h ^= hash_rank[8][p[8]];

	return h;
}

/**
 * Array of shape.
 */
typedef struct {
	unsigned long long *item; /**< dynamic array */
	int n;       /**< number of items in the array */
	int size;    /**< capacity of the array */
} ShapeArray;

/**
 * @brief array initialisation.
 * @param array Array of shapes.
 */
static void shapearray_init(ShapeArray *array)
{
	array->item = NULL;
	array->n = array->size = 0;
}

/**
 * @brief array supression.
 * @param array Array of shapes.
 */
static void shapearray_delete(ShapeArray *array)
{
	free(array->item);
}

/**
 * @brief Append a shape into the array.
 * @param array Array of shapes.
 * @param shape Shape.
 */
static bool shapearray_append(ShapeArray *array, const unsigned long long shape)
{
	int i;

	for (i = 0; i < array->n; ++i) {
		if (array->item[i] == shape) return false;
	}

	if (array->size < array->n + 1) {
		array->item = realloc(array->item, (array->size = (array->size + (array->size >> 1) + 1)) * sizeof (unsigned long long));
		if (array->item == NULL) fatal_error("Cannot re-allocate board array.\n");
	}
	array->item[array->n++] = shape;
	return true;
}


/**
 * HashTable of shapes
 */
typedef struct {
	ShapeArray *array;
	int size;
	int mask;
} ShapeHash;

/**
 * @brief Initialisation of the hash table.
 * @param hash Hash table.
 * @param bitsize Hash table size (as log2(size)).
 */
static void shapehash_init(ShapeHash *hash, int bitsize)
{
	int i;

	hash->size = (1 << bitsize);
	hash->mask = hash->size - 1;
	hash->array = malloc(hash->size * sizeof(PosArray));
	if (hash->array == NULL) fatal_error("Cannot re-allocate board array.\n");
	for (i = 0; i < hash->size; ++i) shapearray_init(hash->array + i);
}

/**
 * @brief Free the hash table.
 * @param hash Hash table.
 */
static void shapehash_delete(ShapeHash *hash)
{
	int i;

	for (i = 0; i < hash->size; ++i) shapearray_delete(hash->array + i);
	free(hash->array);
}

/**
 * @brief Append a shape to the hash table.
 * @param hash Hash table.
 * @param b Position.
 */
static bool shapehash_append(ShapeHash *hash, const Board *b)
{
	unsigned long long u;

	u = shape_unique(b->player | b->opponent);
	return shapearray_append(hash->array + (shape_get_hash_code(u) & hash->mask), u);
}

/**
 * @brief Recursively count shapes.
 * @param hash Hash table.
 * @param board shape.
 * @param depth depth.
 */
static unsigned long long count_shape(ShapeHash *hash, const Board *board, const int depth)
{
	unsigned long long nodes = 0;
	unsigned long long moves;
	int x;
	Board next[1];

	if (shapehash_append(hash, board)) {
		if (depth == 0) return 1;
		moves = get_moves(board->player, board->opponent);

		if (moves) {
			foreach_bit (x, moves) {
				board_next(board, x, next);
				nodes += count_shape(hash, next, depth - 1);
			}
		} else {
			board_next(board, PASS, next);
			nodes += count_shape(hash, next, depth - 1);
		}
	}

	return nodes;
}

/**
 * @brief Count shapes.
 * @param board shape.
 * @param depth depth.
 */
void count_shapes(const Board *board, const int depth)
{
	int i;
	unsigned long long n, c;
	long long t;
	ShapeHash hash;


	board_print(board, BLACK, stdout);
	puts("\n depth       nodes        cumul.        time  speed");
	puts("-------------------------------------------------------");
	c = 1;
	for (i = 1; i <= depth; ++i) {
		shapehash_init(&hash, options.hash_table_size);
		t = -cpu_clock();
		c += (n = count_shape(&hash, board, i));
		t += cpu_clock();
		printf("  %2d, %12llu, %12llu, ", i, n, c);
		time_print(t, stdout);	printf(", ");
		print_scientific(n / (0.001 * t + 0.001), "N/s\n", stdout);
		shapehash_delete(&hash);
	}
	puts("-------------------------------------------------------");
}

